package codetop.dfs;

public class Code105 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return dfs(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    public TreeNode dfs(int []preorder,int preLeft,int preRight,int[]inorder,int left,int right){
        int value=preorder[preLeft];
        TreeNode treeNode=new TreeNode();
        treeNode.val=value;
        int index=0;
        for (int i = left; i <= right; i++) {
            if (value==inorder[i]){
                index=i;
                break;
            }
        }
        int len_left=index-left;
        int len_right=right-index;
        if (len_left>0){
            treeNode.left=dfs(preorder,preLeft+1,preLeft+len_left,inorder,left,left+len_left-1);
        }
        if (len_right>0){
            treeNode.right=dfs(preorder,preRight-len_right,preRight-1,inorder,right-len_right+1,right);
        }
        return treeNode;
    }
}
